package 回溯.不熟;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * todo
 *
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 最近接目标价格的甜点成本1774.java
 * @createTime 2023年03月30日 16:47:00
 */
public class 最近接目标价格的甜点成本1774 {

	private int ret = Integer.MAX_VALUE;
	private int minimum = Integer.MAX_VALUE;

	public int closestCost(int[] baseCosts, int[] toppingCosts, int target) {
		for (int base : baseCosts) {
			backTrack(toppingCosts, base, 0, target);
		}
		return ret;
	}

	private void backTrack(int[] toppingCosts, int price, int curr, int target) {
		if (Math.abs(target - price) == minimum && price < ret || Math.abs(target - price) < minimum) {
			ret = price;
			minimum = Math.abs(target - price);
		}
		if (curr >= toppingCosts.length || price > target) {
			return;
		}
		backTrack(toppingCosts, price, curr + 1, target);
		backTrack(toppingCosts, price + toppingCosts[curr], curr + 1, target);
		backTrack(toppingCosts, price + toppingCosts[curr] * 2, curr + 1, target);
	}
}
